#include <cstdio>
const int MAXN = 100000;
struct node
{
    int data, next;
    node(){
        data = 0;
        next = -1;
    }
} nod[MAXN];
int first_nod, N, K;
int reverse(int first)
{ //这里进行反转操作，借助三个辅助变量
    static int cnt = 0;
    ++cnt; //用于第一次调用时的特殊操作
    int tmaddr = nod[nod[first].next].next;
    int tmnod1 = first;
    int tmnod2 = nod[first].next;
    for (int i = 1; i < K; ++i)
    { //循环n-1次，关键在于不能断链
        nod[tmnod2].next = tmnod1;
        tmnod1 = tmnod2;
        tmnod2 = tmaddr;
        tmaddr = nod[tmnod2].next;
    }
    nod[first].next = tmnod2;
    if (1 == cnt)
    {
        first_nod = tmnod1;
    }
    return tmnod2;
}
bool check(int first)
{ //判断接下来的结点中是否还有K个
    int tmp = first;
    int cnt;
    for (cnt = 0; cnt < K && tmp != -1; ++cnt)
    {
        tmp = nod[tmp].next;
    }
    if (K == cnt)
        return true;
    else
        return false;
}
int main()
{
    scanf("%d%d%d", &first_nod, &N, &K);
    int address;
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &address);
        scanf("%d%d", &nod[address].data, &nod[address].next);
    }
    int ret = first_nod;
    while (check(ret))
    {//因可能会有无效结点，为防止无效操作，故单独用一个函数来判断接下来的序列是否还需要反转
        ret = reverse(ret);
    }
    int tmnod = first_nod;
    while (nod[tmnod].next != -1)
    {
        printf("%05d %d %05d\n", tmnod, nod[tmnod].data, nod[tmnod].next);
        tmnod = nod[tmnod].next;
    }
    printf("%05d %d %d\n", tmnod, nod[tmnod].data, nod[tmnod].next);
    return 0;
}